#pragma once
#include <stack>
#include <string>
#include <regex>
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

class Calculator
{
private:
	stack<int> operands;
	stack<char> operators;

	void calculate()
	{
		char c = operators.top();
		operators.pop();
		if (c == '(')
			operators.push('(');
		else if (c == ')')
		{
			while (operators.top() != '(')
				calculate();
			operators.pop();
		}
		else
		{
			int y = operands.top();
			operands.pop();
			int x = operands.top();
			operands.pop();
			if (c == '+')
				operands.push(x + y);
			else if (c == '-')
				operands.push(x - y);
			else if (c == '*')
				operands.push(x * y);
			else if (c == '/')
				operands.push(x / y);

		}
	}

	int process_input(string input)
	{
		vector<string> tokens;
		istringstream iss(input);
		string str;
		while (getline(iss, str, ' '))
		{
			if (regex_match(str, regex("^-{0,1}[0-9][0-9]*$")))
				operands.push(atoi(str.c_str()));
			else if (regex_match(str, regex("^[-,+,*,/,\\(,\\)]$")))
			{
				if (operators.empty() || get_precedens(operators.top()) < get_precedens(str[0]))
				{
					operators.push(str[0]);
				}
				else if (get_precedens(operators.top()) == get_precedens(str[0]) || get_precedens(operators.top()) > get_precedens(str[0]))
				{
					calculate();
					operators.push(str[0]);
				}
			}
		}
		while (!operators.empty())
			calculate();
		int result = operands.top();
		operands.pop();
		return result;
	}

	int get_precedens(char c)
	{
		if (c == '(' || c == ')')
			return 2;
		else if (c == '*' || c == '/')
			return 1;
		else
			return 0;
	}

public:

	Calculator()
	{
	}

	~Calculator()
	{
	}

	void run()
	{
		while (true)
		{
			string input;
			getline(cin, input);
			if (regex_match(input, regex("^(\\( )*[-]{0,1}((\\( )*[0-9][0-9]*( \\))* [-,+,*,/,\\(,\\)] )*[0-9][0-9]*( \\))*$")))
			{
				if (count(input.begin(), input.end(), '(') != count(input.begin(), input.end(), ')'))
					cout << "Missmatched parentheses" << endl;
				else
					cout << process_input(input) << endl;
			}
			else if (input.compare("exit") == 0)
				break;
			else
				cout << input << ": invalid expression" << endl;
		}
	}
};

